#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "protocol.h"

//For local development and testing only
//#include "graphReader.c"
#include <mpi.h>

void printNodes(int *node) {
	int i = 0;
	for(i = 1; i < node[0]; i = i+2) {
		printf("%d|%d:%d ", i, node[i], node[i+1]);
	}
}

void printWeights(int *weight) {
	int i = 0;
	for(i = 1; i < weight[0]; i += 2) {
			printf("%d|%d:%d ", i, weight[i], weight[i+1]);
	}
}

typedef struct map {
	int name;
	int weight;
	int owner;
} Map;

int *nodelst;
int *weightlst;
int *externallst;
int nodeCount = 0;
int *finalResults;

Map **results;
int resultCount = 0;

_Bool amCompleted = 0;
int Rank;

// For sending MPI message to worker about weight to node
void informWorker(int worker, Map *node) {
	int nw[3];
	nw[0] = externallst[worker];
	nw[1] = externallst[worker+2] + node->weight;
	nw[2] = node->name;

	printf("\033[22;31m%d Sending crawl for %c to %d\n\033[22;37m", Rank, nw[0], externallst[worker+1]);

	MPI_Bsend(nw, 3, MPI_INT, externallst[worker+1], NW, MPI_COMM_WORLD);
}

// Checks if someone has sent the weight to get to a node
// Use force to require a node to be found
// 
// Returns: NULL if no node was found.
Map* checkForNW(_Bool force, Map *n) {
	int nw[3];
	MPI_Status Status;
	int flag;
if(DEBUG) printf("%d Checking for node weight\n", Rank);

	MPI_Iprobe(MPI_ANY_SOURCE, NW, MPI_COMM_WORLD, &flag, &Status);
	if(flag || force) {
		MPI_Recv(nw, 3, MPI_INT, MPI_ANY_SOURCE, NW, MPI_COMM_WORLD, &Status);
		printf("\033[22;32m%d Starting crawl at %c %d from %d\033[22;37m\n", Rank, nw[0], nw[0], Status.MPI_SOURCE);
		n->name = nw[0];
		n->weight = nw[1];
		n->owner = nw[2];
		amCompleted = 0;
		return n;
	}
if(DEBUG) printf("%d Finished Checking for node weight\n", Rank);
	return NULL;
}

// Checks if the given node is liter than current results
// If it is then update the results
// If no result exists for it, create one and say it is liter
Map* isLiter(Map* node) {
	int i = 0;
if(DEBUG) printf("%d Checking is liter %c\n", Rank, node->name);
	for(i = 0; i < resultCount; i++)
		if(results[i]->name == node->name)
			if(results[i]->weight > node->weight) {
if(DEBUG) printf("%d Finished Checking is liter %c from %c for %c\n", Rank, node->name, results[i]->owner, node->owner);
				results[i]->owner = node->owner;
				results[i]->weight = node->weight;
				return results[i];
			} else {
if(DEBUG) printf("%d Finished Checking is liter %c from %c for %c\n", Rank, node->name, node->owner, results[i]->owner);
				return NULL;
			}

	results[i] = malloc(sizeof(Map));
	results[i]->name = node->name;
	results[i]->weight = node->weight;
	results[i]->owner = node->owner;

	resultCount++;
	return results[i];
}

void addNode(Map **store, Map *n, int *count) {
	if(n == NULL) return;

	int nullLocation = 0;

	int i = 0;
	for(i = 0; i < *count; i++) {
		if(store[i] == NULL)
			nullLocation = i;
		else if(store[i]->name == n->name)
			return;
	}

	if(nullLocation)
		store[nullLocation] = n;
	else
		store[i] = n;
if(DEBUG) printf("%d Adding node %c %d\n", Rank, store[i]->name, store[i]->name);
	*count = *count + 1;
}

void removeNode(Map **store, Map *n, int count) {
	if(n == NULL) return;

if(DEBUG) printf("%d Remove node %c\n", Rank, n->name);
	int i = 0;
	for(i = 0; i < count; i++)
		if(store[i] != NULL && store[i]->name == n->name) {
			store[i] = NULL;
			break;
		}
if(DEBUG) printf("%d Remove completed %d %x\n", Rank, i, store[i]);
}

Map* findSmallest(Map **store, int count) {
if(DEBUG) printf("%d Finding Smallest\n", Rank);
	Map *n = store[0];
	int i = 0;
	for(i = 0; i < count; i++) {
		if(n == NULL)
			n = store[i];
		else if(store[i] != NULL && store[i]->weight < n->weight)
			n = store[i];
	}

if(DEBUG) printf("%d Finding Smallest Completed %x %d\n", Rank, n, i);
	return n;
}

void findRange(int name, int *start, int *end) {
	int i = 0;
	for(i = 1; i < nodelst[0]; i += 2) {
		if(nodelst[i] == name) {
			*start = nodelst[i+1];
			*end = nodelst[i+3];
			if(i+2 >= nodelst[0]) {
				*end = weightlst[0];
			}
			return;
		}
	}

	assert(0);
}

// Traverses the links to a given node
void loopOverLink(Map *node) {
	Map *store[nodeCount];
	Map tempNode;
	Map *n;
	int count = 0;
	int start=0, stop=0;
	memset(store, 0, nodeCount);
	store[0] = NULL;
	// If external
	//     informWorker(nw);
	// else if link < results
	//     update stored link
	//
	
	n = isLiter(node);
	// If the external path isn't liter we don't have to traverse
	if(n == NULL) return;

	do {
if(DEBUG) printf("%d crawl %d\n", Rank, count);
if(DEBUG) printf("%d crawling %c\n", Rank, n->name);
		findRange(n->name, &start, &stop);
		int i = 0;
		for(i = start; i < stop; i += 2) {
			if(weightlst[i] == -1) {
				// Pass the slot for externallst, and the parent node
				informWorker(weightlst[i+1], n);
			} else  {
				tempNode.name = nodelst[weightlst[i]];
				tempNode.weight = weightlst[i+1] + n->weight;
				tempNode.owner = n->name;
				addNode(store, isLiter(&tempNode), &count);
			}
		}
		removeNode(store, n, count);
	} while((n = findSmallest(store, count)) != NULL);
if(DEBUG) printf("%d broke out of crawl", Rank);
}

_Bool checkForCompletion() {
if(DEBUG) printf("%d checking completion\n", Rank);
	MPI_Status Status;
	int flag;
	MPI_Iprobe(MPI_ANY_SOURCE, NW, MPI_COMM_WORLD, &flag, &Status);

	if(flag) return 0;
	return 1;
}

// receive the dataset for traversal
void receiveInit() {
	int *arraySize;
	arraySize = malloc(3*sizeof(int));
	MPI_Status Status;
	MPI_Recv(arraySize, 3, MPI_INT, 0, INIT, MPI_COMM_WORLD, &Status);
	nodelst = calloc(arraySize[0],sizeof(int));
	MPI_Recv(nodelst, arraySize[0], MPI_INT, 0, NODES, MPI_COMM_WORLD, &Status);
	weightlst = malloc(arraySize[1]*sizeof(int));
	MPI_Recv(weightlst, arraySize[1], MPI_INT, 0, WEIGHTS, MPI_COMM_WORLD, &Status);
	externallst = malloc(arraySize[2]*sizeof(int));
	MPI_Recv(externallst, arraySize[2], MPI_INT, 0, EXTERNAL, MPI_COMM_WORLD, &Status);

	nodeCount = (nodelst[0]-1)/2;

	results = malloc(nodeCount*sizeof(Map*));
	resultCount = 0;
	free(arraySize);
}

void report() {
	int i = 0;
	int finalSize = resultCount*3;
	finalResults = malloc(finalSize*sizeof(int));
	for(i = 0; i < resultCount; i++) {

		finalResults[i*3] = results[i]->name;
		finalResults[i*3+1] = results[i]->weight;
		finalResults[i*3+2] = results[i]->owner;
	}
	// Send finalResults to moderator
if(DEBUG) printf("Sending ReportSize from proc: %d\n", Rank);
	MPI_Send(&finalSize, 1, MPI_INT, 0, REPORTSIZE, MPI_COMM_WORLD);
//if(DEBUG) printf("Sample Result: %d, %c, %d\n", results[0]->name, results[0]->weight, results[0]->owner);
if(DEBUG) printf("Sending Report from proc: %d\n", Rank);
	MPI_Send(finalResults, finalSize, MPI_INT, 0, REPORT, MPI_COMM_WORLD);
if(DEBUG) printf("%d After Result Send\n", Rank);
}

void cleanup() {
	int i = 0;
	for(i = 0; i < resultCount; i++)
		free(results[i]);

	free(results);
        free(finalResults);
	free(nodelst);
	free(weightlst);
	free(externallst);
}

int main(int argc, char** argv) {
	int Size, scratch, flag, sentDone;
	MPI_Status Status;
	MPI_Init(&argc, &argv);
	MPI_Comm_rank ( MPI_COMM_WORLD, &Rank );
	MPI_Comm_size ( MPI_COMM_WORLD, &Size );

	char *buf;
	int size = 10000;
	MPI_Buffer_attach( malloc(size), size);
	receiveInit();
	Map node;
	Map *n;
	sentDone = 0;

	// Exit when REPORT is sent from proc 0
	while(1) {
		
		n = sentDone ? checkForNW(0, &node) : checkForNW(1, &node);
		if(n != NULL || !sentDone)
			loopOverLink(n);
if(DEBUG) printf("%d finished loop\n", Rank);
		amCompleted = checkForCompletion();
if(DEBUG) printf("%d finished check\n", Rank);
		if(amCompleted && !sentDone)
		{
			// Send DONE to proc 0
if(DEBUG) printf("Sending done the first time from proc: %d\n", Rank);
			MPI_Send(&scratch, 0, MPI_INT, 0, DONE, MPI_COMM_WORLD);
			sentDone = 1;
		}
		sleep(1);

if(DEBUG) printf("%d Prob for Finalize\n", Rank);
		// Receive FINALIZE from moderator
		MPI_Iprobe(0, FINALIZE, MPI_COMM_WORLD, &flag, &Status);
if(DEBUG) printf("%d Done Probing for Finalize\n", Rank);
		if(flag && checkForCompletion())
		{
			MPI_Recv(&scratch, 0, MPI_INT, 0, FINALIZE, MPI_COMM_WORLD, &Status);
if(DEBUG) printf("Sending Done after Finalize from proc: %d\n", Rank);
			MPI_Send(&scratch, 0, MPI_INT, 0, DONE, MPI_COMM_WORLD);
		}
		else if(flag)
		{
			MPI_Recv(&scratch, 0, MPI_INT, 0, FINALIZE, MPI_COMM_WORLD, &Status);
if(DEBUG) printf("Sending Undone after Finalize from proc: %d\n", Rank);
			MPI_Send(&scratch, 0, MPI_INT, 0, UNDONE, MPI_COMM_WORLD);
			sentDone = 0;
		}
			
if(DEBUG) printf("%d Prob for REPORT\n", Rank);
		// Receive REPORT from moderator
		MPI_Iprobe(0, REPORT, MPI_COMM_WORLD, &flag, &Status);
		if(flag)
			break;

if(DEBUG) printf("%d Done Probing for REPORT\n", Rank);
		//sleep(1);
	}

	report();
if(DEBUG) printf("%d Going to Barrier\n", Rank);
//if(DEBUG) printf("%d Barrier\n", Rank);
	MPI_Barrier(MPI_COMM_WORLD);
//if(DEBUG) printf("%d Barrier Not\n", Rank);
	MPI_Buffer_detach( &buf, &size);
	free(buf);
	cleanup();
	MPI_Finalize();
	return 0;
}
